package leetcode;

import java.util.PriorityQueue;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-24 18:10
 **/
public class LeetCode1705 {

    public int eatenApples(int[] apples, int[] days) {
        //可以吃掉的苹果的最大数目
        int res = 0;
        //优先队列存储二元组,第一个元素是苹果的腐烂日期,第二个元素是苹果的个数
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int n = apples.length;
        int i = 0;
        while (i < n) {
            //队列非空,且如果队顶元素达到了腐烂日期,则出队
            while (!pq.isEmpty() && pq.peek()[0] <= i) {
                pq.poll();
            }
            //rottenDay: 腐烂日
            int rottenDay = i + days[i];
            //苹果数量
            int count = apples[i];
            //只有当天生产了苹果,才将其放入到队列中
            if (count > 0) {
                pq.offer(new int[]{rottenDay, count});
            }
            //如果队列非空,吃掉一个苹果,吃掉一个苹果之后数量为0就出队,res+1
            if (!pq.isEmpty()) {
                int[] arr = pq.peek();
                arr[1]--;
                if (arr[1] == 0) {
                    pq.poll();
                }
                res++;
            }
            //天数+1
            i++;
        }

        //第二阶段: 不生产苹果了
        while (!pq.isEmpty()) {
            //出队过期元素
            while (!pq.isEmpty() && pq.peek()[0] <= i) {
                pq.poll();
            }
            //队列为空,直接终止循环
            if (pq.isEmpty()) {
                break;
            }
            //元素出队
            int[] arr = pq.poll();
            //curr表示上面出队元素的苹果在过期前还能吃几天
            int curr = Math.min(arr[0] - i, arr[1]);
            //res+curr:可以吃的苹果数
            res += curr;
            //天数+curr;
            i += curr;
        }
        //返回结果
        return res;
    }

}
